package cn.xaut.贪心算法;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import static java.lang.Math.*;

public class demo435 {

    // 贪心算法
    public int eraseOverlapIntervals3(int[][] intervals) {

        int len = intervals.length;
        if (len == 0)
            return 0;
        
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] != o2[1])
                    return o1[1] - o2[1];
                return o1[0] - o2[0];
            }
        });
        
        int res = 1;
        int pre = 0;
        for (int i = 1; i < len; i++) {
            if (intervals[i][0] >= intervals[pre][1]) {
                res ++;
                pre = i;
            }
        }
        
        return len - res;
    }

        // 动态规划
    public int eraseOverlapIntervals2(int[][] intervals) {

        int len = intervals.length;
        if (len == 0)
            return 0;
        
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0])
                    return o1[0] - o2[0];
                return o1[1] - o2[1];
            }
        });
        
        // dp[i] 表示 intervals[0...i] 的最大没有重叠的子区间的数目
        int[] dp = new int[len];
        Arrays.fill(dp, 1);

        for (int i = 1; i < len; i++) 
            for (int j = 0; j < i; j++) 
                if (intervals[i][0] >= intervals[j][1])
                    dp[i] = max(dp[i], 1 + dp[j]);
            
        int res = 0;
        for (int x : dp)
            res = max(res, x);
        
        return len - res;
    }

    // 未成功的办法
    public int eraseOverlapIntervals(int[][] intervals) {

        if (intervals == null)
            return 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0])
                    return o1[1] - o2[1];
                return o1[0] - o2[0];
            }
        });

        for (int[] ints : intervals) 
            pq.offer(ints);
        
        int[] pre = pq.poll();
        int[] cur;
        int count = 0;
        while (!pq.isEmpty()) {
            cur = pq.poll();
            if (cur[0] == pre[0] || pre[1] > cur[0]) 
                count ++;
            else 
                pre = cur;
        }
        
        return count;
    }

    public static void main(String[] args) {

        System.out.println(new demo435().eraseOverlapIntervals3(new int[][]{{1, 2}, {2, 3}, {3, 4}, {1, 3}}));//1
        System.out.println(new demo435().eraseOverlapIntervals3(new int[][]{{1, 2}, {1, 2}, {1, 2}}));//2
    }
}
